package test2;

import java.util.Arrays;
import java.util.Scanner;

public class Solution3 {// 归并排序
    public static void main(String[] args) {
        System.out.println("请输入需要排序的数字个数（至少为1）：");
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        int[] arr = new int[num];
        System.out.println("请输入需要排序的整数：");
        for (int i = 0; i < num; i++) {
            arr[i] = sc.nextInt();
        }
        mergeSort(arr,0, arr.length - 1);
        System.out.println("排序后结果为：");
        System.out.println(Arrays.toString(arr));
    }

    //递归分解再合并
    private static void mergeSort(int[] arr, int L, int R){
        if (L == R){
            return;
        }
        int M = L + (R - L) / 2;
        mergeSort(arr, L, M);
        mergeSort(arr, M + 1, R);
        merge(arr, L, M, R);
    }

    //合并数据
    private static void merge(int[] arr, int L, int M, int R){
        int LEFT_SIZE = M - L + 1;//将中间元素放入左子数组
        int RIGHT_SIZE = R - M;
        int[] left = new int[LEFT_SIZE];
        int[] right = new int[RIGHT_SIZE];
        int i, j, k;
        //向左子数组添加数据
        for (i = L; i <= M; i++){
            left[i - L] = arr[i];
        }
        //向右子数组添加数据
        for (i = M + 1 ; i <= R; i++){
            right[i - M - 1] = arr[i];
        }
        i = 0; j = 0; k = L;
        //将较小的元素放入原数组
        while (i < LEFT_SIZE && j < RIGHT_SIZE){
            if (left[i] < right[j]){
                arr[k++] = left[i++];
            } else {
                arr[k++] = right[j++];
            }
        }
        //如果有一方没有还没有放完则继续放入
        while (i < LEFT_SIZE){
            arr[k++] = left[i++];
        }
        while (j < RIGHT_SIZE){
            arr[k++] = right[j++];
        }
    }
}
